By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

ALERT ATTENTION: System maintenance will be performed the weekend of Saturday, March 28, 2009. This event will begin at 6:00 am on March 28 and will conclude at approximately 12:00 noon on Sunday March 29 (all times EDT). Some Scitation services may be affected during this period.
Table of Contents
Search This Issue
Volume 36, Issue 3, pp. 563-843

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines

Scott Diehl and Dieter van Melkebeek

pp. 563-594

BibTeX  Abstract Full Text:  PDF

Infinitely-Often Autoreducible Sets

Richard Beigel, Lance Fortnow, and Frank Stephan

pp. 595-608

BibTeX  Abstract Full Text:  PDF

An Extension of the Lovász Local Lemma, and its Applications to Integer Programming

Aravind Srinivasan

pp. 609-634

BibTeX  Abstract Full Text:  PDF

Approximating Longest Cycles in Graphs with Bounded Degrees

Guantao Chen, Zhicheng Gao, Xingxing Yu, and Wenan Zang

pp. 635-656

BibTeX  Abstract Full Text:  PDF

Fairness Measures for Resource Allocation

Amit Kumar and Jon Kleinberg

pp. 657-680

BibTeX  Abstract Full Text:  PDF

Dynamic Subgraph Connectivity with Geometric Applications

Timothy M. Chan

pp. 681-694

BibTeX  Abstract Full Text:  PDF

On the Number of Crossing-Free Matchings, Cycles, and Partitions

Micha Sharir and Emo Welzl

pp. 695-720

BibTeX  Abstract Full Text:  PDF

Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm

Hervé Brönnimann, Lutz Kettner, Michel Pocchiola, and Jack Snoeyink

pp. 721-739

BibTeX  Abstract Full Text:  PDF

Random $k$-SAT: Two Moments Suffice to Cross a Sharp Threshold

Dimitris Achlioptas and Cristopher Moore

pp. 740-762

BibTeX  Abstract Full Text:  PDF

Quantum Algorithms for Some Hidden Shift Problems

Wim van Dam, Sean Hallgren, and Lawrence Ip

pp. 763-778

BibTeX  Abstract Full Text:  PDF

Testing Polynomials over General Fields

Tali Kaufman and Dana Ron

pp. 779-802

BibTeX  Abstract Full Text:  PDF

Exponential Determinization for omega-Automata with a Strong Fairness Acceptance Condition

Shmuel Safra

pp. 803-814

BibTeX  Abstract Full Text:  PDF

Computing Maximally Separated Sets in the Plane

Pankaj K. Agarwal, Mark Overmars, and Micha Sharir

pp. 815-834

BibTeX  Abstract Full Text:  PDF

A Probabilistic Approach to the Dichotomy Problem

Tomasz Luczak and Jaroslav Nesetril

pp. 835-843

BibTeX  Abstract Full Text:  PDF